package com.Questions.BFS;

import java.util.*;
import java.util.ArrayDeque;
import java.util.HashMap;
import java.util.Queue;

/**
 * 腐烂的橘子
 */
public class leetcode994 {
    // 广度有限搜索的路径长度 就是 所经历的最短时间
    // 如果只有一个腐烂的橘子 那么可以直接广度优选搜索 所经历的最短时间 就是新鲜橘子中 腐烂时间的最大值
    // 实际上 腐烂的橘子不止一个 一种是 枚举每一个腐烂的橘子 以它为起点 进行广度有限搜索
    // 另一种是 多源 广度优先 搜索
    // 假设一个超级源点 其层次为 -1 在第一次广度优先搜索的时候
    // 将原本图中的腐烂橘子变成腐烂 这个时候层次为 0
    // 只需要继续进行广度优先搜索 就能正常得到答案
    // 所以 只需要 将原先腐烂的橘子 直接加入到 队列当中即可

    int[] dr = new int[]{-1, 0, 1, 0};
    int[] dc = new int[]{0, -1, 0, 1};
    public int orangesRotting(int[][] grid) {
        int R = grid.length,C = grid[0].length;
        Queue<Integer> queue = new ArrayDeque<Integer>();
        // 使用map 建立 节点 层次 的映射
        Map<Integer, Integer> depth = new HashMap<Integer, Integer>();
        // 将原先 腐烂的橘子 所在位置 直接加入到队列当中
        for (int r = 0; r < R; ++r) {
            for (int c = 0; c < C; ++c) {
                if (grid[r][c] == 2) {
                    int code = r * C + c;// 遍历技巧 使用一个整数 能通过整数除法解出两个整数
                    // 其实标准写法 应该使用一个类型 来存储 横纵坐标
                    queue.add(code);
                    depth.put(code, 0);
                }
            }
        }
        int ans = 0;
        while (!queue.isEmpty()) {
            int code = queue.remove();
            int r = code / C, c = code % C;
            for (int k = 0; k < 4; ++k) { // 遍历 取出的节点的上下左右
                int nr = r + dr[k];
                int nc = c + dc[k];
                if (0 <= nr && nr < R && 0 <= nc && nc < C && grid[nr][nc] == 1) {
                    grid[nr][nc] = 2;
                    int ncode = nr * C + nc;
                    queue.add(ncode);
                    depth.put(ncode,depth.get(code) + 1);
                    // 随之深度的增加 ans一定是自增的
                    ans = depth.get(ncode);
                }
            }
        }

        for (int[] row : grid) {
            for (int v : row) {
                if (v == 1) { // 存在新鲜的橘子
                    return -1;
                }
            }
        }
        return ans;
    }
}
